package chixing.day15.homework.work5;


//用双向链表来储存节点，采用头插法来不断更新顺序；
//        用HashMap来实现来快速查找，查找的时间复杂度为O(1)，空间复杂度为O(n).

import java.util.HashMap;
import java.util.Scanner;

public class LRU_Cache {

    private static class Node {
        private int key, val;
        private Node pre, next;
        Node() {}
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int cap;
    private static int size;
    private static Node dummyHead = new Node();
    private static Node dummyTail = new Node();
    private static HashMap<Integer, Node> map = new HashMap<>();

    private static void add(Node p) {
        Node node = dummyHead.next;
        dummyHead.next = p;
        p.pre = dummyHead;
        p.next = node;
        node.pre = p;
    }
    private static void del(Node p) {
        Node pre = p.pre, next = p.next;
        pre.next = next;
        next.pre = pre;
        p.pre = null;
        p.next = null;
    }
    public static int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node p = map.get(key);
        del(p);
        add(p);
        return p.val;
    }
    public static void put(int key, int val) {
        Node p = new Node(key, val);
        if (map.containsKey(key)) {
            del(map.get(key));
            add(p);
            map.put(key, p);
        }
        else {
            if (size < cap) size++;
            else {
                map.remove(dummyTail.pre.key);
                del(dummyTail.pre);
            }
            add(p);
            map.put(key, p);
        }
    }
    public static void LRU(int capacity) {
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
        cap = capacity;
        size = 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        LRU(sc.nextInt());
        sc.nextLine();
        while (sc.hasNextLine()) {
            String[] op = sc.nextLine().split(" ");
            if (op[0].equals("p"))
                put(Integer.valueOf(op[1]), Integer.valueOf(op[2]));
            else System.out.println(get(Integer.valueOf(op[1])));
        }
    }
}